/****************************************************************************
 * Elisa 1.0                                                                *
 *--------------------------------------------------------------------------*
 * Author: Laurent Granvilliers, Vincent Sorin                              *
 * Copyright (c) 2004 Laboratoire d'Informatique de Nantes Atlantique       *
 *--------------------------------------------------------------------------*
 * Elisa is distributed WITHOUT ANY WARRANTY. Read the associated           *
 * COPYRIGHT file for more details.                                         *
 *--------------------------------------------------------------------------*
 * elisa_interval_optimizer.h                                               *
 ****************************************************************************/

/**
 * @file elisa_interval_optimizer.h
 * @brief Optimization problem = min f s.t. CSP
 */


#ifndef _ELISA_INTERVAL_OPTIMIZER_H
#define _ELISA_INTERVAL_OPTIMIZER_H


#include <vector>
#include "elisa_defs.h"
#include "elisa_solver.h"
#include "elisa_natural_interval_form.h"
#include "elisa_interval_strategy.h"

NAMESPACE_ELISA


class BFSBackTrackStrategy : public BackTrack
{
public:
	BFSBackTrackStrategy() {}

	/**
 	 * strategy algorithm
 	 */
	virtual bool operator()()
	{
		return m_st->discardBox();
	}
};

class BFSMoveStrategy : public Move
{
public:
	BFSMoveStrategy() {}

	/**
 	 * strategy algorithm
 	 */
	virtual bool operator()()
	{
		return !m_st->isEmpty();
	}
};

class ExistenceProver
{
public:
	ExistenceProver (SearchTree & searchTree, AndModel & model)
	{
		_searchTree = &searchTree;
		_model = &model;
		_computable = true;

		SetModelRep::iterator it;
		for (it = model.beginModel(); it != model.endModel(); ++it) {
			ConstraintHandler *ch = static_cast<ConstraintHandler *>(*it);
			RealConstraint *c = static_cast<RealConstraint *>(ch->getConstraint());
			RealConstraintRelation *bc = new RealConstraintRelation(c, new NaturalIntervalFormFactory());
			_vec.push_back(bc);
		}
	}

	ExistenceProver (SearchTree & st, RealConstraint & c)
	{
		_searchTree = &st;
		_computable = true;

		RealConstraintRelation *bc = new RealConstraintRelation(&c, new NaturalIntervalFormFactory());
		_vec.push_back(bc);
	}

	bool exists() const
	{
		Box *mid = _searchTree->toPoint();

		if (_computable) {
			for (unsigned int i = 0; i < _vec.size(); ++i) {
				if (!(_vec[i]->isCertainlySatisfied(mid))) {
					delete mid;
					return false;
				}
			}
			delete mid;
			return true;
		}
		delete mid;
		return false;
	}

private:
	AndModel *_model;  // the model
	SearchTree *_searchTree;
	bool _computable;
	std::vector<RealConstraintRelation * > _vec;
};

/**
 * @ingroup SearchTree
 * @class IntervalOptimizer
 * @brief Global optimization algorithm
 */
class IntervalOptimizer : public Solver
{
public:
	/// Exception class
	class BadModelType { };

	/**
 	 * Constructor: each solver is associated to a model
 	 * @param model Constraints' model
 	 * @param f the expression to maximize
 	 * @param cform factory for interval form
 	 */
	IntervalOptimizer(Model & mo, const RealExpr & f) throw (BadModelType) 
		: Solver(&mo, new BFSBackTrackStrategy(), new BFSMoveStrategy())
	{
		bool goodType = false;
		RealConstraint *rc = 0;
		m_model = &mo;
		AndModel *model = dynamic_cast<AndModel *>(mo.model());

		ConstraintHandler *ch = dynamic_cast<ConstraintHandler *>(mo.model());
		if (ch != 0) {
			rc = dynamic_cast<RealConstraint *>(ch->getConstraint());
		}

		SetModelRep::iterator it;
		if (model != 0) {
			goodType = true;
			for (it = model->beginModel(); (it != model->endModel()) && goodType; ++it) {
				ConstraintHandler *ch = dynamic_cast<ConstraintHandler *>(*it);
				if (ch == 0) {
					goodType = false;
				} else {
					if (dynamic_cast<RealConstraint *>(ch->getConstraint()) == 0) {
						goodType = false;
					}
				}
			}
		}

		if ((!goodType) && (rc == 0)) {
			throw BadModelType();
		}

		// Creation of existence prover
		if (model != 0) {
			_prover = new ExistenceProver(m_searchTree, *model);
		}
		if (rc != 0) {
			_prover = new ExistenceProver(m_searchTree, *rc);
		}

		// Use of BFS strategy
		m_searchTree.setBFS();

		// Creation of an interval form of the objective function
		_createForm = new NaturalIntervalFormFactory();
		_f = _createForm->create(&f);
	}

	/**
 	 * Destructor
 	 * @post the factory for the intervalForm is deleted
 	 */
	~IntervalOptimizer ()
	{
		delete _createForm;
		delete _prover;
		delete _f;
	}


	/**
 	 * Returns the lastly computed minimum
 	 */
	Interval minimum() const
	{
		return _minimum;
	}


	/**
 	 * Use of the splitting strategy SearchMaxInterval
 	 */
	void useSearchMaxInterval()
	{
		//delete _chooseVar;
		Solver::useChoiceStrategy(new SearchMaxInterval());
	}


	/**
 	 * Use of the splitting strategy SearchRoundRobin
 	 */
	void useSearchRoundRobin()
	{
		//      delete _chooseVar;
		Solver::useChoiceStrategy(new SearchRoundRobin);
	}



	/**
 	 * @brief Computes the next solution
 	 * @return false if there is no more solution
 	 */
	bool next();


private:
	IntervalForm *_f;              // objective function
	IntervalFormFactory *_createForm; // creation of interval form
	ExistenceProver *_prover;      // existence proof of solution in a box
	Interval::Bound _min;          // reliable bound of min(_f)
	std::vector<Box *> _sol;       // vector of small boxes
	Interval _minimum;             // the lastly computed minimum

	/// Called by next when all the global optima have been computed in _sol
	bool end();
};
END_NAMESPACE_ELISA
#endif // ELISA_INTERVAL_OPTIMIZER
